bzoj1010 장난감 포장 [결정 단조성 최적화 dp]

하나의 모범 문제라고 할 수 있다.우리는 먼저 소박한 dp방정식을 얻을 수 있다. f[i]=min(f[j]+w(j,i)),j∈[0,i). w(j,i)는 j+1~i를 포장하여 운송하는 비용의 시간 복잡도는 O(n2)라고 표시한다. 그리고 표를 작성하면 의사결정의 단조성을 만족시킬 수 있기 때문에 단조로운 대기열로 의사결정점을 유지하고 2분의 1을 의사결정점으로 하는 구간을 찾으면 된다. 시간의...

bzoj동적 계획 최적화